#include <vector>
#include <unordered_set>
#include <queue>
#include "../9.2-Graph/02-graph_adj_list.h"

using namespace std;

/* 深度优先遍历 DFS */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
vector<Vertex*> graphDFS(GraphAdjList& graph, Vertex* startVet) {
    vector<Vertex*> res;
    unordered_set<Vertex*> visited;
    dfs(graph, visited, res, startVet);
    return res;
}

/* 深度优先遍历 DFS 辅助函数 */
void dfs(GraphAdjList& graph, unordered_set<Vertex*>& visited, vector<Vertex*>& res, Vertex* vet) {
    res.push_back(vet);
    visited.emplace(vet);
    for (Vertex* adjVet : graph.adjList[vet]) {
        if (visited.count(adjVet))
            continue;
        dfs(graph, visited, res, adjVet);
    }
}
